package sortedset

import "math/rand"

const (
	maxLevel = 16
)

type Element struct {
	Member string
	Score  float64
}

type Level struct {
	forward *node
	span    int64
}
type node struct {
	Element
	backward *node
	level    []*Level
}
type skiplist struct {
	head   *node
	tail   *node
	length int64
	level  int16
}

func makeNode(member string, score float64, level int16) *node {
	n := &node{
		Element: Element{
			Member: member,
			Score:  score,
		},
		level: make([]*Level, level),
	}
	for i := range n.level {
		n.level[i] = new(Level)
	}
	return n
}

func makeSkiplist() *skiplist {
	return &skiplist{
		head:  makeNode("", 0, maxLevel),
		level: 1,
	}
}

func randomLevel() int16 {
	level := int16(1)
	for float32(rand.Int31()&0xFFFF) < (0.25 * 0xFFFF) {
		level++
	}
	if level > maxLevel {
		return maxLevel
	}
	return level
}

func (skiplist *skiplist) insert(member string, score float64) *node {
	// update记录每一层的前驱节点
	prevs := make([]*node, maxLevel)
	// rank记录每一层前驱节点的排名
	rank := make([]int64, maxLevel)

	// find position to insert
	curr := skiplist.head
	for i := skiplist.level - 1; i >= 0; i-- {
		if i == skiplist.level-1 {
			rank[i] = 0
		} else {
			rank[i] = rank[i+1]
		}
		if curr.level[i] != nil {
			for curr.level[i].forward != nil && (curr.level[i].forward.Score < score || curr.level[i].forward.Score == score && curr.level[i].forward.Member < member) {
				rank[i] += curr.level[i].span
				curr = curr.level[i].forward
			}
		}
		prevs[i] = curr
	}

	level := randomLevel()
	// 加层
	if level > skiplist.level {
		for i := skiplist.level; i < level; i++ {
			prevs[i] = skiplist.head
			rank[i] = 0
			prevs[i].level[i].span = skiplist.length
		}
		skiplist.level = level
	}
	// insert
	node := makeNode(member, score, level)
	for i := int16(0); i < level; i++ {
		node.level[i].forward = prevs[i].level[i].forward
		prevs[i].level[i].forward = node

		// update span covered by update[i] as node is inserted here
		node.level[i].span = prevs[i].level[i].span - (rank[0] - rank[i])
		prevs[i].level[i].span = rank[0] - rank[i] + 1
	}

	// increment span for untouched levels
	for i := level; i < skiplist.level; i++ {
		prevs[i].level[i].span++
	}

	// set backward node
	if prevs[0] == skiplist.head {
		node.backward = nil
	} else {
		node.backward = prevs[0]
	}

	if node.level[0].forward != nil {
		node.level[0].forward.backward = node
	} else {
		skiplist.tail = node
	}
	skiplist.length++
	return node
}

/*
 * param node: node to delete
 * param prevs: prev node (of target)
 */
func (skiplist *skiplist) removeNode(node *node, prevs []*node) {
	for i := int16(0); i < skiplist.level; i++ {
		if prevs[i].level[i].forward == node {
			prevs[i].level[i].span += node.level[i].span - 1
			prevs[i].level[i].forward = node.level[i].forward
		}else {
			prevs[i].level[i].span--
		}
	}
	if node.level[0].forward != nil {
		node.level[0].forward.backward = node.backward
	}else {
		skiplist.tail = node.backward
	}
	for skiplist.level > 1 && skiplist.head.level[skiplist.level-1].forward == nil {
		skiplist.level --
	}
	skiplist.length--
}


/*
 * return: has found and removed node
 */
func (skiplist *skiplist) remove(member string, score float64) bool {
	/*
	 * find backward node (of target) or last node of each level
	 * their forward need to be updated
	 */
	prevs := make([]*node, maxLevel)
	curr := skiplist.head
	for i := skiplist.level - 1; i >= 0;i-- {
		for curr.level[i].forward != nil && (curr.level[i].forward.Score < score || curr.level[i].forward.Score == score && curr.level[i].forward.Member < member) {
			curr = curr.level[i].forward
		}
		prevs[i] = curr
	}
	curr = curr.level[0].forward
	if curr != nil && curr.Member == member && curr.Score == score {
		skiplist.removeNode(curr, prevs)
		return true
	}
	return false
}

/*
 * return: 1 based rank, 0 means member not found
 */

func (skiplist *skiplist) getRank(member string, score float64) int64  {
	var rank int64
	curr := skiplist.head
	for i := skiplist.level - 1; i >= 0;i-- {
		for curr.level[i].forward != nil && (curr.level[i].forward.Score < score || curr.level[i].forward.Score == score && curr.level[i].forward.Member <= member) {
			rank += curr.level[i].span
			curr = curr.level[i].forward
		}
	}
	if curr.Member == member {
		return rank
	}
	return 0
}

/*
 * 1-based rank
 */
func (skiplist *skiplist) getByRank(rank int64) *node {
	var cnt int64
	curr := skiplist.head
	for i := skiplist.level - 1; i >= 0;i -- {
		for curr.level[i].forward != nil && (cnt + curr.level[i].span) <= rank {
			cnt += curr.level[i].span
			curr = curr.level[i].forward
		}
		if cnt == rank {
			return curr
		}
	}
	return nil
}

func (skiplist *skiplist) hasInRange(min *ScoreBorder, max *ScoreBorder) bool  {
	// min & max = empty
	if min.Value > max.Value || (min.Value == max.Value && (min.Exclude || max.Exclude)) {
		return false
	}
	// min > tail
	n := skiplist.tail
	if n == nil || !min.less(n.Score) {
		return false
	}
	// max < head
	n = skiplist.head.level[0].forward
	if n == nil || !max.greater(n.Score) {
		return false
	}
	return true
}


func (skiplist *skiplist) getFirstInScoreRange(min *ScoreBorder, max *ScoreBorder) *node {
	if !skiplist.hasInRange(min, max) {
		return nil
	}
	n := skiplist.head
	for i := skiplist.level - 1; i >= 0;i -- {
		for n.level[i].forward != nil && !min.less(n.level[i].forward.Score) {
			n = n.level[i].forward
		}
	}
	n = n.level[0].forward
	if !max.greater(n.Score) {
		return nil
	}
	return n
}

func (skiplist *skiplist) getLastInScoreRange(min *ScoreBorder, max *ScoreBorder) *node {
	if !skiplist.hasInRange(min, max) {
		return nil
	}
	n := skiplist.head
	// scan from top level
	for i := skiplist.level - 1; i >= 0; i-- {
		for n.level[i].forward != nil && max.greater(n.level[i].forward.Score) {
			n = n.level[i].forward
		}
	}
	if !min.less(n.Score) {
		return nil
	}
	return n
}

/*
 * return removed elements
 */
func (skiplist *skiplist) RemoveRangeByScore(min *ScoreBorder, max *ScoreBorder) (removed []*Element)  {
	prevs := make([]*node, maxLevel)
	n := skiplist.head
	for i := skiplist.level - 1; i >= 0; i-- {
		for n.level[i].forward != nil && !min.less(n.level[i].forward.Score) {
			n = n.level[i].forward
		}
		prevs[i] = n
	}
	n = n.level[0].forward

	for n != nil && max.greater(n.Score){
		nxt := n.level[0].forward
		removed = append(removed, &n.Element)
		skiplist.removeNode(n,prevs)
		n = nxt
	}
	return removed
}

// 1-based rank, including start, exclude stop
func (skiplist *skiplist) RemoveRangeByRank(start int64, stop int64) (removed []*Element)  {
	var cnt int64
	prevs := make([]*node, maxLevel)

	n := skiplist.head
	for i := skiplist.level - 1; i >= 0;i -- {
		for n.level[i].forward != nil && (cnt + n.level[i].span) < start {
			cnt += n.level[i].span
			n = n.level[i].forward
		}
		prevs[i] = n
	}
	n = n.level[0].forward
	cnt++
	for n != nil && cnt < stop {
		nxt := n.level[0].forward
		removed = append(removed, &n.Element)
		skiplist.removeNode(n, prevs)
		n = nxt
		cnt++
	}
	return removed
}





















































